package arithmetic.sort;

/**
 * Created by jiangfeng on 2017/10/10.
 * 归并排序
 */
public class MergeSort {
    public static void mergeSort(Integer[] arr) {
        int[] temp = new int[arr.length];// 统一新建一个临时数组，避免反复新建消耗性能
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(Integer[] arr, int left, int right, int[] temp) {
        if (left < right) {// 边界，两个元素
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);
            sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(Integer[] arr, int left, int mid, int right, int[] temp){
        int l = left; // 左数组指针
        int r = mid+1; // 右数组指针
        int i = 0; // 临时数组指针
        // 比较两有序数组的头，选取小的放进temp数组中
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                temp[i++] = arr[l++];
            } else {
                temp[i++] = arr[r++];
            }
        }
        // 把未完成的有序数组也放入temp中
        while (l <= mid) {
            temp[i++] = arr[l++];
        }
        while (r <= right) {
            temp[i++] = arr[r++];
        }
        // 复制temp到 arr中,利用r指针
        while (i > 0) {
            arr[--r] = temp[--i];
        }
    }

}
